9. 分页
上一节 讲解了分段这一尝试提高物理内存利用率的方法。但我们知道，碎片化是分段这种将空间切成不同大小的段的方法一个不可避免的问题。因此，解决碎片化的根本方法是不采用分段，相反地，我们考虑将空间切分成固定长度的分片，把物理内存看成是这些定长槽块的阵列。这种思想被称作 分页，而这些定长块被称作 页帧。
基本思想
操作系统将进程的地址空间与整个物理内存都划分成大量大小相同的页帧，随后指定进程地址空间的某一页对应物理内存中的另一页。操作系统通过 页表（Page Table） 跟踪这种对应关系。页表就是一种用于将虚拟地址映射到物理地址的数据结构。一般而言每个进程都有一个对应的页表（某些特殊的页表除外，见下文倒排页表）。其原理是：虚拟空间中的每一个地址都可以被分解为 虚拟页面号（Virtual Page Number，VPN） 与 偏移量（Offset） 两个部分。通过检索页表查询虚拟页面号所对应的 物理帧号（Physical Frame Number，PFN），就能得到地址空间中的这一页具体存放在物理内存的哪一块上，从而将虚拟地址转换为物理地址，由于虚拟页与物理页的大小相同，在此过程中偏移量是保持不变的。
页表的内容
页表只是一种数据结构，其存储着虚拟页号（VPN）到物理帧（页）号（PFN）的映射关系。具体的组织方式多种多样，我们先讲解最简单的线性页表的形式：就是一个数组，其中存储的元素被称作 页表项（Page Entry Number，PTE）。操作系统通过 VPN 检索对应的 PTE 来获得期望的 PFN。
例如，x86 架构下的一个 PTE 结构如下图所示：
除了 PFN 外，一个 PTE 还包含大量的标志位，负责对该物理页的属性做标注，具体而言：
- 有效位（
P）：用于指示特定地址转换是否位于物理内存中。1= 在内存中，有效；0= 不在内存中，无效。此处的无效有两种可能：可能页面被交换到磁盘；可能确实是无效页面。无论何种情况下，进程尝试访问无效的页会触发 缺页异常（Page Fault） 陷入操作系统，操作系统可能会从磁盘调入对应的页，也可能直接终止程序。 - 保护位（
R/W）：用于指示该页面是否可写。1= 可读可写；0= 可读。 - 访问特权级位(
U/S)：用于定义页面的访问特权级。1= 用户模式可访问；0= 仅内核模式可访问。 - 硬件缓存位（
PWT、PCD、PAT）：用于控制硬件缓存的工作。 - 访问位（
A）：用于指示该页是否被读取或写入。1= 曾被访问。0= 未被访问。 - 脏位（
D)：用于指示页面被带入内存后是否被修改过。1= 曾被修改。0= 未被修改。 - 全局位（
G）：用于指示该页是否全局共享，用于跨进程的 TLB 缓存共享中。
页表是现代操作系统的内存管理子系统中最重要的数据结构之一，存储虚拟地址到物理地址的转换。操作系统需要页表知道地址空间中的每个页驻留在内存中的何处，对每一个地址空间都是如此。然而，页表的确切结构由特定的硬件（在旧系统中）与操作系统（现代系统）确定或管理。
优缺点
分页的优点显而易见，其中一大优点是 灵活性：操作系统此时无需关心进程如何使用空间（例如堆栈区的使用与各自的增长方向），因此可以提供更加高效的地址空间抽象。此外，操作系统管理空闲空间也变简单了，此时它只需要维护物理内存上所有页的空闲情况即可。
然而，一个页的大小并不大，这意味着物理内存可以划分出巨量的页，进而页表会变得很大。例如，x86 架构下页的典型大小为 4 KB。就算系统是 32 位机最多只能寻址 4 GB 内存，这也意味着页表需要维护物理内存中
正因为页表停留在内存中，平凡的分页实现的读取速度很慢。这是因为此时对于每个内存引用都因为分页多出了一次内存读取的开销：首先读取页表，将虚拟地址转换为物理地址；随后依据转换出的物理地址读物内存。因此我们必须对分页加以改进。
加快速度：TLB
由于每一次内存引用都需要访问一次页表，为如此频繁的访问操作增添硬件缓冲可以大大加快这一转换速度。这就是 地址转换旁路缓冲存储器（Translation Lookaside Buffer，TLB） 要实现的目标，它充当频繁发生的虚拟地址到物理地址的转换的硬件缓存。对每次内存访问，首先提取虚拟地址的 VPN，检查 TLB 中是否有该 VPN 到 PFN 的映射缓存，如果 TLB 命中，则直接从 TLB 中取出结果组合上偏移量后快速完成物理地址的转换；如果 TLB 未命中，再去内存中查询页表，并用结果更新 TLB 后重新尝试执行指令。由于 TLB 位于 CPU 附近，访问速度远高于内存，只要 TLB 缓存命中率高，就可以省下大量的内存访问开销，加快程序运行速度。
缓存是计算机系统中最基本的性能改进技术之一，其基本思想是“让常见的情况更快”。缓存能够加速运行的前提是指令与数据引用的 局部性（Locality），分为两种：时间局部性 与 空间局部性。时间局部性指的是最近访问过的指令与数据可能会在短期内再度被访问；空间局部性是指当程序访问内存的某一地址时，可能很快会继续访问该地址附近的内存。例如，循环中的代码与数据具有很强的时间局部性；数组等数据连续存放在内存中的数据结构具有很强的空间局部性。而链表的空间局部性就很差，因此顺序遍历数组与链表的时间复杂度虽然都是
无论是何者（指令、数据或地址转换）的硬件缓存都利用了局部性，在小而快的高速缓存中保存一份副本，允许处理器先检查这些缓存，只要有期望的结果，就能在几个时钟周期内快速获得想要的数据，而不是耗费几 ns 访问内存。
我们用缓存的 命中率 来衡量缓存的性能，其指的是一段时间内缓存成功填充内容请求的比例。优化提高缓存命中率可以显著提高程序运行速度。一般而言，程序的局部性越强，缓存命中率就越高。因此编写程序时也需要注意缓存对性能的影响，以期编写出理论时间复杂度相同但实际运行效率更高的程序。这部分的具体内容见 CSAPP 6.5 编写高速缓存友好的代码。
除此之外，由于存储器的不可能三角，这样的高速缓存容量不可能很大。
典型的 TLB 有 32 项、64 项或 128 项。TLB 是一种 全相联缓存，即页表中的任意地址映射项可映射到 TLB 中的任意位置，无固定映射规则。硬件 并行 遍历整个 TLB 以获取所需的数据。一条 TLB 项至少需要包括 VPN、PFN 与其它标志位。标志位可能包括：
- 有效位：指示该缓存项是否有效。
- 保护位、脏位：含义同 PTE 中的对应位。
- 地址空间标识符（Address Spacer Identifier，ASID）：负责标识该缓存项属于哪一个地址空间，实现跨上下文切换的 TLB 共享。
一条无效的 PTE 代表该物理页没有被进程申请使用，程序尝试访问这些页会触发异常中断。然而一条无效的 TLB 项只是代表一条无效的地址映射缓存，进程的页表中很有可能记录了实际的转换关系，只是还没有被 TLB 缓存下来而已。例如，系统启动时所有的 TLB 项的有效位都被置为无效，随着进程运行，TLB 会慢慢被有效的缓存项充满。通过将 TLB 项设置为无效，操作系统可以避免进程不会错误使用前一个运行进程的地址映射。
我们来详细解释一下 ASID。由于操作系统为每个进程维护一个页表，每个进程的页表都不尽相同，因此 TLB 中缓存的 VPN 到 PFN 的映射只对当前运行的进程有效，一旦发生进程切换，操作系统与硬件必须确保新进程不会错误使用前一个运行进程的地址映射。
一种解决方法很简单粗暴，在发生上下文切换时直接清空 TLB 即可。但其缺点在于每次新进程运行时都会遭遇大量的 TLB 未命中导致必须大量访问内存中的页表来填充 TLB，拖慢了运行时间。因此另一种方法是添加硬件支持，使得 TLB 可以跨上下文共享，例如一种常见的实现方法是添加 ASID（一般为 8 位）。操作系统为每个进程维护一个 ASID，进行上下文切换时通过特权指令将对应的寄存器设置为将要运行进程的 ASID。硬件可以根据当前运行进程的 ASID 寻找合适的 TLB 项。
除此之外，ASID 还允许 TLB 中出现不同进程的不同 VPN 指向同一个 PFN，实现物理内存在多个进程内共享甚至是全局共享，这对系统中的共享库是很有用的：共享库此时只需在内存中存在一份，但可以被所有进程使用，减少了内存开销。